<!DOCTYPE html>
<html lang="">
    <head><meta charset='utf-8'>
<meta name='viewport' content='width=device-width, initial-scale=1'>
<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js">
</script><meta name='description' content='时间复杂度为o(nlogn)的算法 1.归并排序 算法描述 ​	归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。
归并排序是用分治思想，分治模式在每一层递归上有三个步骤：
 分解（Divide）：将n个元素分成个含n/2个元素的子序列。 解决（Conquer）：用合并排序法对两个子序列递归的排序。 合并（Combine）：合并两个已排序的子序列已得到排序结果。  简单来说，归并排序的核心思想就是将数组的元素不断的拆分成最小项，然后再不断的比较合并，最终整合成一个整体有序的数组。  
动图演示 （点击查看）
 
代码示例 本实例中使用的是递归法。
private static int[] arr;//使用时记得初始化数组 public static void mergeSort(int[] nums,int lo,int hi){ if (hi&amp;lt;=lo){ return; } int mid=lo&#43;(hi-lo)/2; //左子组拆分  mergeSort(nums,lo,mid); //右子组拆分  mergeSort(nums,mid&#43;1,hi); //合并  merge(nums,lo,mid,hi); } public static void merge(int[] nums,int lo,int mid,int hi){ int i=lo; int left=lo; int right=mid&#43;1; while (left&amp;lt;=mid&amp;amp;&amp;amp;right&amp;lt;=hi){ if (nums[left]&amp;lt;nums[right]){ arr[i&#43;&#43;]=nums[left&#43;&#43;]; }else { arr[i&#43;&#43;]=nums[right&#43;&#43;]; } } while (left&amp;lt;=mid){ arr[i&#43;&#43;]=nums[left&#43;&#43;]; } while (right&amp;lt;=hi){ arr[i&#43;&#43;]=nums[right&#43;&#43;]; } //将辅助数组复制到原数组  for (int j = lo; j &amp;lt;=hi ; j&#43;&#43;) { nums[j]=arr[j]; } } ​	通过代码我们可以看到，归并排序需要借助一个辅助的数组帮助我们去合并有序的数组，因此额外的空间复杂度为O(n)。因为我们在遇到相等的数据的时候必然是按顺序“抄写”到辅助数组上的，所以，归并排序同样是稳定算法。'><title>排序算法（二）</title>

<link rel='canonical' href='http://example.org/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/'>

<link rel="stylesheet" href="/scss/style.min.css"><meta property='og:title' content='排序算法（二）'>
<meta property='og:description' content='时间复杂度为o(nlogn)的算法 1.归并排序 算法描述 ​	归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。
归并排序是用分治思想，分治模式在每一层递归上有三个步骤：
 分解（Divide）：将n个元素分成个含n/2个元素的子序列。 解决（Conquer）：用合并排序法对两个子序列递归的排序。 合并（Combine）：合并两个已排序的子序列已得到排序结果。  简单来说，归并排序的核心思想就是将数组的元素不断的拆分成最小项，然后再不断的比较合并，最终整合成一个整体有序的数组。  
动图演示 （点击查看）
 
代码示例 本实例中使用的是递归法。
private static int[] arr;//使用时记得初始化数组 public static void mergeSort(int[] nums,int lo,int hi){ if (hi&amp;lt;=lo){ return; } int mid=lo&#43;(hi-lo)/2; //左子组拆分  mergeSort(nums,lo,mid); //右子组拆分  mergeSort(nums,mid&#43;1,hi); //合并  merge(nums,lo,mid,hi); } public static void merge(int[] nums,int lo,int mid,int hi){ int i=lo; int left=lo; int right=mid&#43;1; while (left&amp;lt;=mid&amp;amp;&amp;amp;right&amp;lt;=hi){ if (nums[left]&amp;lt;nums[right]){ arr[i&#43;&#43;]=nums[left&#43;&#43;]; }else { arr[i&#43;&#43;]=nums[right&#43;&#43;]; } } while (left&amp;lt;=mid){ arr[i&#43;&#43;]=nums[left&#43;&#43;]; } while (right&amp;lt;=hi){ arr[i&#43;&#43;]=nums[right&#43;&#43;]; } //将辅助数组复制到原数组  for (int j = lo; j &amp;lt;=hi ; j&#43;&#43;) { nums[j]=arr[j]; } } ​	通过代码我们可以看到，归并排序需要借助一个辅助的数组帮助我们去合并有序的数组，因此额外的空间复杂度为O(n)。因为我们在遇到相等的数据的时候必然是按顺序“抄写”到辅助数组上的，所以，归并排序同样是稳定算法。'>
<meta property='og:url' content='http://example.org/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/'>
<meta property='og:site_name' content='我的技术小屋'>
<meta property='og:type' content='article'><meta property='article:section' content='Post' /><meta property='article:tag' content='排序算法' /><meta property='article:published_time' content='2022-01-11T00:00:00&#43;00:00'/><meta property='article:modified_time' content='2022-01-11T00:00:00&#43;00:00'/><meta property='og:image' content='http://example.org/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/aa.jfif' />
<meta name="twitter:title" content="排序算法（二）">
<meta name="twitter:description" content="时间复杂度为o(nlogn)的算法 1.归并排序 算法描述 ​	归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。
归并排序是用分治思想，分治模式在每一层递归上有三个步骤：
 分解（Divide）：将n个元素分成个含n/2个元素的子序列。 解决（Conquer）：用合并排序法对两个子序列递归的排序。 合并（Combine）：合并两个已排序的子序列已得到排序结果。  简单来说，归并排序的核心思想就是将数组的元素不断的拆分成最小项，然后再不断的比较合并，最终整合成一个整体有序的数组。  
动图演示 （点击查看）
 
代码示例 本实例中使用的是递归法。
private static int[] arr;//使用时记得初始化数组 public static void mergeSort(int[] nums,int lo,int hi){ if (hi&amp;lt;=lo){ return; } int mid=lo&#43;(hi-lo)/2; //左子组拆分  mergeSort(nums,lo,mid); //右子组拆分  mergeSort(nums,mid&#43;1,hi); //合并  merge(nums,lo,mid,hi); } public static void merge(int[] nums,int lo,int mid,int hi){ int i=lo; int left=lo; int right=mid&#43;1; while (left&amp;lt;=mid&amp;amp;&amp;amp;right&amp;lt;=hi){ if (nums[left]&amp;lt;nums[right]){ arr[i&#43;&#43;]=nums[left&#43;&#43;]; }else { arr[i&#43;&#43;]=nums[right&#43;&#43;]; } } while (left&amp;lt;=mid){ arr[i&#43;&#43;]=nums[left&#43;&#43;]; } while (right&amp;lt;=hi){ arr[i&#43;&#43;]=nums[right&#43;&#43;]; } //将辅助数组复制到原数组  for (int j = lo; j &amp;lt;=hi ; j&#43;&#43;) { nums[j]=arr[j]; } } ​	通过代码我们可以看到，归并排序需要借助一个辅助的数组帮助我们去合并有序的数组，因此额外的空间复杂度为O(n)。因为我们在遇到相等的数据的时候必然是按顺序“抄写”到辅助数组上的，所以，归并排序同样是稳定算法。"><meta name="twitter:card" content="summary_large_image">
    <meta name="twitter:image" content='http://example.org/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/aa.jfif' />
    <link rel="shortcut icon" href="/img/%e7%bc%85%e5%9b%a0%e7%8c%ab.png" />
<style>
    :root {
        --article-font-family: "Noto Serif SC", var(--base-font-family);
    }
</style>

<script> 
		(function () {
		    const customFont = document.createElement('link');
		    customFont.href = "https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@300;700&display=swap"; 
		    customFont.type = "text/css";
		    customFont.rel = "stylesheet";
		
		    document.head.appendChild(customFont);
		}());
</script>
    </head>
    <body class="
    article-page has-toc
">
    <script>
        (function() {
            const colorSchemeKey = 'StackColorScheme';
            if(!localStorage.getItem(colorSchemeKey)){
                localStorage.setItem(colorSchemeKey, "auto");
            }
        })();
    </script><script>
    (function() {
        const colorSchemeKey = 'StackColorScheme';
        const colorSchemeItem = localStorage.getItem(colorSchemeKey);
        const supportDarkMode = window.matchMedia('(prefers-color-scheme: dark)').matches === true;

        if (colorSchemeItem == 'dark' || colorSchemeItem === 'auto' && supportDarkMode) {
            

            document.documentElement.dataset.scheme = 'dark';
        } else {
            document.documentElement.dataset.scheme = 'light';
        }
    })();
</script>
<div class="container main-container flex 
    
        extended
    
">
    
        <div id="article-toolbar">
            <a href="/" class="back-home">
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-chevron-left" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <polyline points="15 6 9 12 15 18" />
</svg>



                <span>Back</span>
            </a>
        </div>
    
<main class="main full-width">
    <article class="has-image main-article">
    <header class="article-header">
        <div class="article-image">
            <a href="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/">
                <img src="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/aa_huc032c4d09cfc3260a681c94ccd0382c2_189778_800x0_resize_q75_box.jfif"
                        srcset="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/aa_huc032c4d09cfc3260a681c94ccd0382c2_189778_800x0_resize_q75_box.jfif 800w, /post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/aa_huc032c4d09cfc3260a681c94ccd0382c2_189778_1600x0_resize_q75_box.jfif 1600w"
                        width="800" 
                        height="450" 
                        loading="lazy"
                        alt="Featured image of post 排序算法（二）" />
                
            </a>
        </div>
    

    <div class="article-details">
    
    <header class="article-category">
        
            <a href="/categories/%E7%AE%97%E6%B3%95/" >
                算法
            </a>
        
    </header>
    

    <h2 class="article-title">
        <a href="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/">排序算法（二）</a>
    </h2>

    

    
    <footer class="article-time">
        
            <div>
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-calendar-time" width="56" height="56" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <path d="M11.795 21h-6.795a2 2 0 0 1 -2 -2v-12a2 2 0 0 1 2 -2h12a2 2 0 0 1 2 2v4" />
  <circle cx="18" cy="18" r="4" />
  <path d="M15 3v4" />
  <path d="M7 3v4" />
  <path d="M3 11h16" />
  <path d="M18 16.496v1.504l1 1" />
</svg>
                <time class="article-time--published">Jan 11, 2022</time>
            </div>
        

        
            <div>
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-clock" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="12" cy="12" r="9" />
  <polyline points="12 7 12 12 15 15" />
</svg>



                <time class="article-time--reading">
                    3 minute read
                </time>
            </div>
        
    </footer>
    
</div>
</header>

    <section class="article-content">
    <h2 id="时间复杂度为onlogn的算法">时间复杂度为o(nlogn)的算法</h2>
<h3 id="1归并排序">1.归并排序</h3>
<h4 id="算法描述">算法描述</h4>
<p>​		归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。</p>
<p>归并排序是用分治思想，分治模式在每一层递归上有三个步骤：</p>
<ul>
<li><strong>分解（Divide）</strong>：将n个元素分成个含n/2个元素的子序列。</li>
<li><strong>解决（Conquer）</strong>：用合并排序法对两个子序列递归的排序。</li>
<li><strong>合并（Combine）</strong>：合并两个已排序的子序列已得到排序结果。</li>
</ul>
<p><strong>简单来说，归并排序的核心思想就是将数组的元素不断的拆分成最小项，然后再不断的比较合并，最终整合成一个整体有序的数组。</strong>
<figure 
	
		class="gallery-image" 
		style="
			flex-grow: 130; 
			flex-basis: 313px"
	>
	<a href="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/%E5%88%86%E6%B2%BB.png" data-size="1768x1354">
		<img src="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/%E5%88%86%E6%B2%BB.png"
			width="1768"
			height="1354"
			srcset="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/%E5%88%86%E6%B2%BB_hub32da92fb60ea6c3ba32ffd3fb6e0658_162876_480x0_resize_box_3.png 480w, /post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/%E5%88%86%E6%B2%BB_hub32da92fb60ea6c3ba32ffd3fb6e0658_162876_1024x0_resize_box_3.png 1024w"
			loading="lazy"
			>
	</a>
	
</figure></p>
<h4 id="动图演示">动图演示</h4>
<p>（点击查看）</p>
<p><figure 
	
		class="gallery-image" 
		style="
			flex-grow: 160; 
			flex-basis: 385px"
	>
	<a href="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/%E5%BD%92%E5%B9%B6.gif" data-size="811x505">
		<img src="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/%E5%BD%92%E5%B9%B6.gif"
			width="811"
			height="505"
			srcset="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/%E5%BD%92%E5%B9%B6_hu729ef34a72840c3a28ceee3bbc26585a_274178_480x0_resize_box.gif 480w, /post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/%E5%BD%92%E5%B9%B6_hu729ef34a72840c3a28ceee3bbc26585a_274178_1024x0_resize_box.gif 1024w"
			loading="lazy"
			>
	</a>
	
</figure></p>
<h4 id="代码示例">代码示例</h4>
<p>本实例中使用的是递归法。</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-java" data-lang="java"><span style="color:#66d9ef">private</span> <span style="color:#66d9ef">static</span> <span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> arr<span style="color:#f92672">;</span><span style="color:#75715e">//使用时记得初始化数组
</span><span style="color:#75715e"></span><span style="color:#66d9ef">public</span> <span style="color:#66d9ef">static</span> <span style="color:#66d9ef">void</span> <span style="color:#a6e22e">mergeSort</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> nums<span style="color:#f92672">,</span><span style="color:#66d9ef">int</span> lo<span style="color:#f92672">,</span><span style="color:#66d9ef">int</span> hi<span style="color:#f92672">){</span>
        <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>hi<span style="color:#f92672">&lt;=</span>lo<span style="color:#f92672">){</span>
            <span style="color:#66d9ef">return</span><span style="color:#f92672">;</span>
        <span style="color:#f92672">}</span>
        <span style="color:#66d9ef">int</span> mid<span style="color:#f92672">=</span>lo<span style="color:#f92672">+(</span>hi<span style="color:#f92672">-</span>lo<span style="color:#f92672">)/</span>2<span style="color:#f92672">;</span>
		<span style="color:#75715e">//左子组拆分
</span><span style="color:#75715e"></span>        mergeSort<span style="color:#f92672">(</span>nums<span style="color:#f92672">,</span>lo<span style="color:#f92672">,</span>mid<span style="color:#f92672">);</span>
		<span style="color:#75715e">//右子组拆分
</span><span style="color:#75715e"></span>        mergeSort<span style="color:#f92672">(</span>nums<span style="color:#f92672">,</span>mid<span style="color:#f92672">+</span>1<span style="color:#f92672">,</span>hi<span style="color:#f92672">);</span>
		<span style="color:#75715e">//合并
</span><span style="color:#75715e"></span>        merge<span style="color:#f92672">(</span>nums<span style="color:#f92672">,</span>lo<span style="color:#f92672">,</span>mid<span style="color:#f92672">,</span>hi<span style="color:#f92672">);</span>

    <span style="color:#f92672">}</span>
    <span style="color:#66d9ef">public</span> <span style="color:#66d9ef">static</span> <span style="color:#66d9ef">void</span> <span style="color:#a6e22e">merge</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> nums<span style="color:#f92672">,</span><span style="color:#66d9ef">int</span> lo<span style="color:#f92672">,</span><span style="color:#66d9ef">int</span> mid<span style="color:#f92672">,</span><span style="color:#66d9ef">int</span> hi<span style="color:#f92672">){</span>

        <span style="color:#66d9ef">int</span> i<span style="color:#f92672">=</span>lo<span style="color:#f92672">;</span>
        <span style="color:#66d9ef">int</span> left<span style="color:#f92672">=</span>lo<span style="color:#f92672">;</span>
        <span style="color:#66d9ef">int</span> right<span style="color:#f92672">=</span>mid<span style="color:#f92672">+</span>1<span style="color:#f92672">;</span>
        <span style="color:#66d9ef">while</span> <span style="color:#f92672">(</span>left<span style="color:#f92672">&lt;=</span>mid<span style="color:#f92672">&amp;&amp;</span>right<span style="color:#f92672">&lt;=</span>hi<span style="color:#f92672">){</span>
            <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>nums<span style="color:#f92672">[</span>left<span style="color:#f92672">]&lt;</span>nums<span style="color:#f92672">[</span>right<span style="color:#f92672">]){</span>
                arr<span style="color:#f92672">[</span>i<span style="color:#f92672">++]=</span>nums<span style="color:#f92672">[</span>left<span style="color:#f92672">++];</span>
            <span style="color:#f92672">}</span><span style="color:#66d9ef">else</span> <span style="color:#f92672">{</span>
                arr<span style="color:#f92672">[</span>i<span style="color:#f92672">++]=</span>nums<span style="color:#f92672">[</span>right<span style="color:#f92672">++];</span>
            <span style="color:#f92672">}</span>
        <span style="color:#f92672">}</span>
        <span style="color:#66d9ef">while</span> <span style="color:#f92672">(</span>left<span style="color:#f92672">&lt;=</span>mid<span style="color:#f92672">){</span>
            arr<span style="color:#f92672">[</span>i<span style="color:#f92672">++]=</span>nums<span style="color:#f92672">[</span>left<span style="color:#f92672">++];</span>
        <span style="color:#f92672">}</span>
        <span style="color:#66d9ef">while</span> <span style="color:#f92672">(</span>right<span style="color:#f92672">&lt;=</span>hi<span style="color:#f92672">){</span>
            arr<span style="color:#f92672">[</span>i<span style="color:#f92672">++]=</span>nums<span style="color:#f92672">[</span>right<span style="color:#f92672">++];</span>
        <span style="color:#f92672">}</span>
		<span style="color:#75715e">//将辅助数组复制到原数组
</span><span style="color:#75715e"></span>        <span style="color:#66d9ef">for</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> j <span style="color:#f92672">=</span> lo<span style="color:#f92672">;</span> j <span style="color:#f92672">&lt;=</span>hi <span style="color:#f92672">;</span> j<span style="color:#f92672">++)</span> <span style="color:#f92672">{</span>
            nums<span style="color:#f92672">[</span>j<span style="color:#f92672">]=</span>arr<span style="color:#f92672">[</span>j<span style="color:#f92672">];</span>
        <span style="color:#f92672">}</span>
    <span style="color:#f92672">}</span>
</code></pre></div><p>​		通过代码我们可以看到，归并排序需要借助一个辅助的数组帮助我们去合并有序的数组，因此额外的空间复杂度为<code>O(n)</code>。因为我们在遇到相等的数据的时候必然是按顺序“抄写”到辅助数组上的，所以，归并排序同样是稳定算法。</p>
<h3 id="2快速排序">2.快速排序</h3>
<h4 id="算法描述-1">算法描述</h4>
<p>​		快速排序由于排序效率在同为<code>O(N*logN)</code>的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想&mdash;-分治法也确实实用，因此很多软件公司的笔试面试，很多知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。</p>
<p>​		<strong>排序算法的思想非常简单，在待排序的数列中，我们首先要找一个数字作为基准数（这只是个专用名词）。为了方便，我们一般选择第 （1 或最后一个）数字作为基准数（其实选择第几个并没有关系）。接下来我们需要把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序的数列的右边。这时，左右两个分区的元素就相对有序了；接着把两个分区的元素分别按照上面两种方法继续对每个分区找出基准数，然后移动，直到各个分区只有一个数时为止。</strong></p>
<p><figure 
	
		class="gallery-image" 
		style="
			flex-grow: 255; 
			flex-basis: 613px"
	>
	<a href="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/%E5%BF%AB%E6%8E%92.png" data-size="2148x840">
		<img src="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/%E5%BF%AB%E6%8E%92.png"
			width="2148"
			height="840"
			srcset="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/%E5%BF%AB%E6%8E%92_huac125b7916d25a3a18d5f3bb04f7dae0_110759_480x0_resize_box_3.png 480w, /post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/%E5%BF%AB%E6%8E%92_huac125b7916d25a3a18d5f3bb04f7dae0_110759_1024x0_resize_box_3.png 1024w"
			loading="lazy"
			>
	</a>
	
</figure></p>
<h4 id="动图演示-1">动图演示</h4>
<p>（点击查看）</p>
<p><figure 
	
		class="gallery-image" 
		style="
			flex-grow: 321; 
			flex-basis: 772px"
	>
	<a href="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/%E5%BF%AB%E9%80%9F.gif" data-size="811x252">
		<img src="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/%E5%BF%AB%E9%80%9F.gif"
			width="811"
			height="252"
			srcset="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/%E5%BF%AB%E9%80%9F_hu4d44be5cb710bf76364ae9284e6f595c_276065_480x0_resize_box.gif 480w, /post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/%E5%BF%AB%E9%80%9F_hu4d44be5cb710bf76364ae9284e6f595c_276065_1024x0_resize_box.gif 1024w"
			loading="lazy"
			>
	</a>
	
</figure></p>
<h4 id="代码实例">代码实例</h4>
<p>​		从算法的描述和动图的演示，我们可以将每次在找小于等于和大于该基数的过程称作<code>partition</code>过程，我们可以利用插入排序的思想去模拟这个过程，从左到右去维护一个小于等于<code>基数</code>的区间，从而达到一个<code>partition</code>的一个过程。如图：</p>
<p><figure 
	
		class="gallery-image" 
		style="
			flex-grow: 127; 
			flex-basis: 306px"
	>
	<a href="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/partation.png" data-size="454x356">
		<img src="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/partation.png"
			width="454"
			height="356"
			srcset="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/partation_hu99b5180d0462d1c0f963e3cf6443456a_8830_480x0_resize_box_3.png 480w, /post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%BA%8C/partation_hu99b5180d0462d1c0f963e3cf6443456a_8830_1024x0_resize_box_3.png 1024w"
			loading="lazy"
			>
	</a>
	
</figure></p>
<p>先定义一个用于交换的方法，以便复用：</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-java" data-lang="java"><span style="color:#66d9ef">public</span> <span style="color:#66d9ef">static</span> <span style="color:#66d9ef">void</span> <span style="color:#a6e22e">swap</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> nums<span style="color:#f92672">,</span><span style="color:#66d9ef">int</span> i<span style="color:#f92672">,</span><span style="color:#66d9ef">int</span> j<span style="color:#f92672">){</span>
       <span style="color:#66d9ef">int</span> temp<span style="color:#f92672">=</span>nums<span style="color:#f92672">[</span>i<span style="color:#f92672">];</span>
       nums<span style="color:#f92672">[</span>i<span style="color:#f92672">]=</span>nums<span style="color:#f92672">[</span>j<span style="color:#f92672">];</span>
       nums<span style="color:#f92672">[</span>j<span style="color:#f92672">]=</span>temp<span style="color:#f92672">;</span>
    <span style="color:#f92672">}</span>
</code></pre></div><h5 id="代码实例1">代码实例1</h5>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-java" data-lang="java">	<span style="color:#66d9ef">public</span> <span style="color:#66d9ef">static</span> <span style="color:#66d9ef">void</span> <span style="color:#a6e22e">quickSort1</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> arr<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
		<span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>arr <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span> <span style="color:#f92672">||</span> arr<span style="color:#f92672">.</span><span style="color:#a6e22e">length</span> <span style="color:#f92672">&lt;</span> 2<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
			<span style="color:#66d9ef">return</span><span style="color:#f92672">;</span>
		<span style="color:#f92672">}</span>
		process1<span style="color:#f92672">(</span>arr<span style="color:#f92672">,</span> 0<span style="color:#f92672">,</span> arr<span style="color:#f92672">.</span><span style="color:#a6e22e">length</span> <span style="color:#f92672">-</span> 1<span style="color:#f92672">);</span>
	<span style="color:#f92672">}</span>


	<span style="color:#66d9ef">public</span> <span style="color:#66d9ef">static</span> <span style="color:#66d9ef">void</span> <span style="color:#a6e22e">process1</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> arr<span style="color:#f92672">,</span> <span style="color:#66d9ef">int</span> L<span style="color:#f92672">,</span> <span style="color:#66d9ef">int</span> R<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
		<span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>L <span style="color:#f92672">&gt;=</span> R<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
			<span style="color:#66d9ef">return</span><span style="color:#f92672">;</span>
		<span style="color:#f92672">}</span>
		<span style="color:#75715e">// L..R partition arr[R] [ &lt;=arr[R] arr[R] &gt;arr[R] ]
</span><span style="color:#75715e"></span>		<span style="color:#66d9ef">int</span> M <span style="color:#f92672">=</span> partition<span style="color:#f92672">(</span>arr<span style="color:#f92672">,</span> L<span style="color:#f92672">,</span> R<span style="color:#f92672">);</span>
		process1<span style="color:#f92672">(</span>arr<span style="color:#f92672">,</span> L<span style="color:#f92672">,</span> M <span style="color:#f92672">-</span> 1<span style="color:#f92672">);</span>
		process1<span style="color:#f92672">(</span>arr<span style="color:#f92672">,</span> M <span style="color:#f92672">+</span> 1<span style="color:#f92672">,</span> R<span style="color:#f92672">);</span>
	<span style="color:#f92672">}</span>

	<span style="color:#75715e">// arr[L..R]上，以arr[R]位置的数做划分值
</span><span style="color:#75715e"></span>	<span style="color:#75715e">// &lt;= X &gt; X
</span><span style="color:#75715e"></span>	<span style="color:#75715e">// &lt;= X X
</span><span style="color:#75715e"></span>	<span style="color:#66d9ef">public</span> <span style="color:#66d9ef">static</span> <span style="color:#66d9ef">int</span> <span style="color:#a6e22e">partition</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> arr<span style="color:#f92672">,</span> <span style="color:#66d9ef">int</span> L<span style="color:#f92672">,</span> <span style="color:#66d9ef">int</span> R<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
		<span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>L <span style="color:#f92672">&gt;</span> R<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
		  <span style="color:#66d9ef">return</span> <span style="color:#f92672">-</span>1<span style="color:#f92672">;</span>
		<span style="color:#f92672">}</span>
		<span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>L <span style="color:#f92672">==</span> R<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
		  <span style="color:#66d9ef">return</span> L<span style="color:#f92672">;</span>
		<span style="color:#f92672">}</span>
		<span style="color:#66d9ef">int</span> lessEqual <span style="color:#f92672">=</span> L <span style="color:#f92672">-</span> 1<span style="color:#f92672">;</span>
		<span style="color:#66d9ef">int</span> index <span style="color:#f92672">=</span> L<span style="color:#f92672">;</span>
		<span style="color:#66d9ef">while</span> <span style="color:#f92672">(</span>index <span style="color:#f92672">&lt;</span> R<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
		  <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>arr<span style="color:#f92672">[</span>index<span style="color:#f92672">]</span> <span style="color:#f92672">&lt;=</span> arr<span style="color:#f92672">[</span>R<span style="color:#f92672">])</span> <span style="color:#f92672">{</span>
		   swap<span style="color:#f92672">(</span>arr<span style="color:#f92672">,</span> index<span style="color:#f92672">,</span> <span style="color:#f92672">++</span>lessEqual<span style="color:#f92672">);</span>
		  <span style="color:#f92672">}</span>
		  index<span style="color:#f92672">++;</span>
		<span style="color:#f92672">}</span>
		swap<span style="color:#f92672">(</span>arr<span style="color:#f92672">,</span> <span style="color:#f92672">++</span>lessEqual<span style="color:#f92672">,</span> R<span style="color:#f92672">);</span>
		<span style="color:#66d9ef">return</span> lessEqual<span style="color:#f92672">;</span>
	<span style="color:#f92672">}</span>
</code></pre></div><p>​		快速排序的时间复杂度为<code>O(logn)</code>,并且不具备稳定性，在最坏的情况下快速排序是会回退到时间复杂度为O(n²)的时间复杂度。为什么这么说呢？我们回到<code>partation</code>过程，倘若数据存在以下情况：</p>
<ol>
<li>数组已经是正序（same order）排过序的。</li>
<li>数组已经是倒序排过序的。</li>
<li>所有的元素都相同（1、2)的特殊情况。
经过<code>partation</code>过程<code>基数</code>为最大或者最小数字，那么所有数都划分到一个序列去了 时间复杂度为O(n²)。</li>
</ol>
<p><strong>优化一：</strong></p>
<p>因此我们可以选取一个数据中的随机值和<code>基数</code>位置的值进行交换，从而大大的避免了最坏情况的发生。</p>
<p><strong>优化二：</strong></p>
<p>并且我们还可以在<code>实例1</code>中进行进一步优化，每次<code>partation</code>过程都是维护小于等于的区间，那么在等于基数值的部分是会重复的计算。因此可以去维护两个区间一个小于区间、一个大于区间，在<code>partation</code>过程返回的就是一个小于基数的边界值和一个大于基数的边界值，这样就可以使等于基数值的部分不再进行重复的计算。</p>
<h5 id="代码实例2">代码实例2</h5>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-java" data-lang="java"><span style="color:#66d9ef">public</span> <span style="color:#66d9ef">static</span> <span style="color:#66d9ef">void</span> <span style="color:#a6e22e">quickSort2</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> arr<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
		<span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>arr <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span> <span style="color:#f92672">||</span> arr<span style="color:#f92672">.</span><span style="color:#a6e22e">length</span> <span style="color:#f92672">&lt;</span> 2<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
			<span style="color:#66d9ef">return</span><span style="color:#f92672">;</span>
		<span style="color:#f92672">}</span>
		process3<span style="color:#f92672">(</span>arr<span style="color:#f92672">,</span> 0<span style="color:#f92672">,</span> arr<span style="color:#f92672">.</span><span style="color:#a6e22e">length</span> <span style="color:#f92672">-</span> 1<span style="color:#f92672">);</span>
	<span style="color:#f92672">}</span>

	<span style="color:#66d9ef">public</span> <span style="color:#66d9ef">static</span> <span style="color:#66d9ef">void</span> <span style="color:#a6e22e">process2</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> arr<span style="color:#f92672">,</span> <span style="color:#66d9ef">int</span> L<span style="color:#f92672">,</span> <span style="color:#66d9ef">int</span> R<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
		<span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>L <span style="color:#f92672">&gt;=</span> R<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
			<span style="color:#66d9ef">return</span><span style="color:#f92672">;</span>
		<span style="color:#f92672">}</span>
		swap<span style="color:#f92672">(</span>arr<span style="color:#f92672">,</span> L <span style="color:#f92672">+</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">)</span> <span style="color:#f92672">(</span>Math<span style="color:#f92672">.</span><span style="color:#a6e22e">random</span><span style="color:#f92672">()</span> <span style="color:#f92672">*</span> <span style="color:#f92672">(</span>R <span style="color:#f92672">-</span> L <span style="color:#f92672">+</span> 1<span style="color:#f92672">)),</span> R<span style="color:#f92672">);</span>
		<span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> equalArea <span style="color:#f92672">=</span> netherlandsFlag<span style="color:#f92672">(</span>arr<span style="color:#f92672">,</span> L<span style="color:#f92672">,</span> R<span style="color:#f92672">);</span>
		process3<span style="color:#f92672">(</span>arr<span style="color:#f92672">,</span> L<span style="color:#f92672">,</span> equalArea<span style="color:#f92672">[</span>0<span style="color:#f92672">]</span> <span style="color:#f92672">-</span> 1<span style="color:#f92672">);</span>
		process3<span style="color:#f92672">(</span>arr<span style="color:#f92672">,</span> equalArea<span style="color:#f92672">[</span>1<span style="color:#f92672">]</span> <span style="color:#f92672">+</span> 1<span style="color:#f92672">,</span> R<span style="color:#f92672">);</span>
	<span style="color:#f92672">}</span>
	
	<span style="color:#75715e">//partation过程
</span><span style="color:#75715e"></span>	<span style="color:#66d9ef">public</span> <span style="color:#66d9ef">static</span> <span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> <span style="color:#a6e22e">netherlandsFlag</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> arr<span style="color:#f92672">,</span> <span style="color:#66d9ef">int</span> L<span style="color:#f92672">,</span> <span style="color:#66d9ef">int</span> R<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
		<span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>L <span style="color:#f92672">&gt;</span> R<span style="color:#f92672">)</span> <span style="color:#f92672">{</span> <span style="color:#75715e">// L...R L&gt;R
</span><span style="color:#75715e"></span>			<span style="color:#66d9ef">return</span> <span style="color:#66d9ef">new</span> <span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> <span style="color:#f92672">{</span> <span style="color:#f92672">-</span>1<span style="color:#f92672">,</span> <span style="color:#f92672">-</span>1 <span style="color:#f92672">};</span>
		<span style="color:#f92672">}</span>
		<span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>L <span style="color:#f92672">==</span> R<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
			<span style="color:#66d9ef">return</span> <span style="color:#66d9ef">new</span> <span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> <span style="color:#f92672">{</span> L<span style="color:#f92672">,</span> R <span style="color:#f92672">};</span>
		<span style="color:#f92672">}</span>
		<span style="color:#66d9ef">int</span> less <span style="color:#f92672">=</span> L <span style="color:#f92672">-</span> 1<span style="color:#f92672">;</span> <span style="color:#75715e">// &lt; 区 右边界
</span><span style="color:#75715e"></span>		<span style="color:#66d9ef">int</span> more <span style="color:#f92672">=</span> R<span style="color:#f92672">;</span> <span style="color:#75715e">// &gt; 区 左边界
</span><span style="color:#75715e"></span>		<span style="color:#66d9ef">int</span> index <span style="color:#f92672">=</span> L<span style="color:#f92672">;</span>
		<span style="color:#66d9ef">while</span> <span style="color:#f92672">(</span>index <span style="color:#f92672">&lt;</span> more<span style="color:#f92672">)</span> <span style="color:#f92672">{</span> <span style="color:#75715e">// 当前位置，不能和 &gt;区的左边界撞上
</span><span style="color:#75715e"></span>			<span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>arr<span style="color:#f92672">[</span>index<span style="color:#f92672">]</span> <span style="color:#f92672">==</span> arr<span style="color:#f92672">[</span>R<span style="color:#f92672">])</span> <span style="color:#f92672">{</span>
				index<span style="color:#f92672">++;</span>
			<span style="color:#f92672">}</span> <span style="color:#66d9ef">else</span> <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>arr<span style="color:#f92672">[</span>index<span style="color:#f92672">]</span> <span style="color:#f92672">&lt;</span> arr<span style="color:#f92672">[</span>R<span style="color:#f92672">])</span> <span style="color:#f92672">{</span>
<span style="color:#75715e">//				swap(arr, less + 1, index);
</span><span style="color:#75715e">//				less++;
</span><span style="color:#75715e">//				index++;						
</span><span style="color:#75715e"></span>				swap<span style="color:#f92672">(</span>arr<span style="color:#f92672">,</span> index<span style="color:#f92672">++,</span> <span style="color:#f92672">++</span>less<span style="color:#f92672">);</span>
			<span style="color:#f92672">}</span> <span style="color:#66d9ef">else</span> <span style="color:#f92672">{</span> <span style="color:#75715e">// &gt;
</span><span style="color:#75715e"></span>				swap<span style="color:#f92672">(</span>arr<span style="color:#f92672">,</span> index<span style="color:#f92672">,</span> <span style="color:#f92672">--</span>more<span style="color:#f92672">);</span>
			<span style="color:#f92672">}</span>
		<span style="color:#f92672">}</span>
		swap<span style="color:#f92672">(</span>arr<span style="color:#f92672">,</span> more<span style="color:#f92672">,</span> R<span style="color:#f92672">);</span> <span style="color:#75715e">// &lt;[R]   =[R]   &gt;[R]
</span><span style="color:#75715e"></span>		<span style="color:#66d9ef">return</span> <span style="color:#66d9ef">new</span> <span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> <span style="color:#f92672">{</span> less <span style="color:#f92672">+</span> 1<span style="color:#f92672">,</span> more <span style="color:#f92672">};</span>
	<span style="color:#f92672">}</span>
</code></pre></div><p>最终优化的代码就完成了，快速排序是十分重要的，尤其是它的<code>partation</code>过程。</p>

</section>


    <footer class="article-footer">
    
    <section class="article-tags">
        
            <a href="/tags/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/">排序算法</a>
        
    </section>


    </footer>


    
</article>

    <aside class="related-contents--wrapper">
    
    
        <h2 class="section-title">Related contents</h2>
        <div class="related-contents">
            <div class="flex article-list--tile">
                
                    
<article class="has-image">
    <a href="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/">
        
        
            <div class="article-image">
                <img src="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/aa.dd4f9fe02c59caa4ba7e228b8c61c446_huc032c4d09cfc3260a681c94ccd0382c2_189778_250x150_fill_q75_box_smart1.jfif" 
                        width="250" 
                        height="150" 
                        loading="lazy" 
                        data-key="排序算法" 
                        data-hash="md5-3U&#43;f4CxZyqS6fiKLjGHERg==">
                
            </div>
        

        <div class="article-details">
            <h2 class="article-title">排序算法（一）</h2>
        </div>
    </a>
</article>
                
            </div>
        </div>
    
</aside>

     
    
        
    

    <script src="https://s3.pstatp.com/cdn/expire-1-M/jquery/3.2.1/jquery.min.js"></script>
        <script>
        function color_tags() {
            var colorArr = ["#428BCA", "#AEDCAE", "#ECA9A7", "#DA99FF", "#FFB380", "#D9B999"];
            $('.tagCloud-tags a').each(function () {
                try {
                    tagsColor = colorArr[Math.floor(Math.random() * colorArr.length)];
                    $(this).css("background", tagsColor); 
                }
                catch (err) { }
            });
        }

        $(document).ready(function () {
            color_tags()
        });
    </script>
    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

<footer class="site-footer">
<span id="busuanzi_container_site_uv">
    本站总访问量<span id="busuanzi_value_site_uv"></span>次
</span>
    <section class="copyright">
        &copy; 
        
        2022zp妙妙屋·<i class="fas fa-bell"></i> <a id="days">0</a>Days<br>共叭叭了 3682字·共 16篇文章</br><span><p>
    </section>
    <div style="width:300px;margin:0 auto; padding:20px 0;">
    <a href="https://beian.miit.gov.cn/，" rel="external nofollow" target="_blank"><p style="float:left;height:20px;line-height:20px;margin: 0px 0px 0px 25px; color:#939393;">京ICP备2022000201号-1</p></a></span>
		 		<a target="_blank" href="http://www.beian.gov.cn/portal/registerSystemInfo?recordcode=11011102001825" style="display:inline-block;text-decoration:none;height:20px;line-height:20px;"><img src="/beian.png" style="float:left;"/><p style="float:left;height:20px;line-height:20px;margin: 0px 0px 0px 5px; color:#939393;">京公网安备 11011102001825号</p></a>
	</div>
    <section class="powerby">
        Built with <a href="https://gohugo.io/" target="_blank" rel="noopener">Hugo</a> <br />
        Theme <b><a href="https://github.com/CaiJimmy/hugo-theme-stack" target="_blank" rel="noopener" data-version="3.5.0">Stack</a></b> designed by <a href="www.zpzp.vip" target="_blank" rel="noopener">ZP</a>
    </section>
</footer>



    
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

    
    <div class="pswp__bg"></div>

    
    <div class="pswp__scroll-wrap">

        
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>

        
        <div class="pswp__ui pswp__ui--hidden">

            <div class="pswp__top-bar">

                

                <div class="pswp__counter"></div>

                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>

                <button class="pswp__button pswp__button--share" title="Share"></button>

                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>

                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>

                
                
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                        <div class="pswp__preloader__cut">
                            <div class="pswp__preloader__donut"></div>
                        </div>
                    </div>
                </div>
            </div>

            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div>
            </div>

            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>

            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>

            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>

        </div>

    </div>

</div><script 
                src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.js"integrity="sha256-ePwmChbbvXbsO02lbM3HoHbSHTHFAeChekF1xKJdleo="crossorigin="anonymous"
                defer="true"
                >
            </script><script 
                src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe-ui-default.min.js"integrity="sha256-UKkzOn/w1mBxRmLLGrSeyB4e1xbrp4xylgAWb3M42pU="crossorigin="anonymous"
                defer="true"
                >
            </script><link 
                rel="stylesheet" 
                href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/default-skin/default-skin.css"integrity="sha256-c0uckgykQ9v5k&#43;IqViZOZKc47Jn7KQil4/MP3ySA3F8="crossorigin="anonymous"
            ><link 
                rel="stylesheet" 
                href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.css"integrity="sha256-SBLU4vv6CA6lHsZ1XyTdhyjJxCjPif/TRkjnsyGAGnE="crossorigin="anonymous"
            >

            </main>
    
        <aside class="sidebar right-sidebar sticky">
            <section class="widget archives">
                <div class="widget-icon">
                    <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-hash" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <line x1="5" y1="9" x2="19" y2="9" />
  <line x1="5" y1="15" x2="19" y2="15" />
  <line x1="11" y1="4" x2="7" y2="20" />
  <line x1="17" y1="4" x2="13" y2="20" />
</svg>



                </div>
                <h2 class="widget-title section-title">Table of contents</h2>
                
                <div class="widget--toc">
                    <nav id="TableOfContents">
  <ul>
    <li><a href="#时间复杂度为onlogn的算法">时间复杂度为o(nlogn)的算法</a>
      <ul>
        <li><a href="#1归并排序">1.归并排序</a></li>
        <li><a href="#2快速排序">2.快速排序</a></li>
      </ul>
    </li>
  </ul>
</nav>
                </div>
            </section>
        </aside>
    

        </div>
        <script 
                src="https://cdn.jsdelivr.net/npm/node-vibrant@3.1.5/dist/vibrant.min.js"integrity="sha256-5NovOZc4iwiAWTYIFiIM7DxKUXKWvpVEuMEPLzcm5/g="crossorigin="anonymous"
                defer="false"
                >
            </script><script type="text/javascript" src="/ts/main.js" defer></script>
<script>
    (function () {
        const customFont = document.createElement('link');
        customFont.href = "https://fonts.googleapis.com/css2?family=Lato:wght@300;400;700&display=swap";

        customFont.type = "text/css";
        customFont.rel = "stylesheet";

        document.head.appendChild(customFont);
    }());
</script>

<script
    src="https://cdn.jsdelivr.net/gh/zhixuan2333/gh-blog@v0.1.0/js/ribbon.min.js"
    integrity="sha384-UEK8ZiP3VgFNP8KnKMKDmd4pAUAOJ59Y2Jo3ED2Z5qKQf6HLHovMxq7Beb9CLPUe"
    crossorigin="anonymous"
    size="300"
    alpha="0.6"
    zindex="-1"
    defer
></script>
<script
    src="https://cdn.jsdelivr.net/gh/zhixuan2333/gh-blog@v0.1.0/js/nprogress.min.js"
    integrity="sha384-bHDlAEUFxsRI7JfULv3DTpL2IXbbgn4JHQJibgo5iiXSK6Iu8muwqHANhun74Cqg"
    crossorigin="anonymous"
></script>
<link
    rel="stylesheet"
    href="https://cdn.jsdelivr.net/gh/zhixuan2333/gh-blog@v0.1.0/css/nprogress.css"
    integrity="sha384-KJyhr2syt5+4M9Pz5dipCvTrtvOmLk/olWVdfhAp858UCa64Ia5GFpTN7+G4BWpE"
    crossorigin="anonymous"
/>
<script src="/js/snow.js"></script>
<script>
    NProgress.start();
    document.addEventListener("readystatechange", () => {
        if (document.readyState === "interactive") NProgress.inc(0.8);
        if (document.readyState === "complete") NProgress.done();
    });
</script>

    </body>
</html>
